class Solution {//leetcode97——交错字符串
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size(),n=s2.size(),k=s3.size();
        if(k!=m+n) return false;

        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0]=true;
        s1=" "+s1;
        s2=" "+s2;
        s3=" "+s3;
        
        for(int j=1;j<n+1;j++){
            if(s2[j]==s3[j]) dp[0][j]=true;
            else break;
        }
        for(int i=1;i<m+1;i++){
            if(s1[i]==s3[i]) dp[i][0]=true;
            else break;
        }
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(s1[i]==s3[i+j]) dp[i][j]=dp[i-1][j];
                if(s2[j]==s3[i+j]) dp[i][j]=dp[i][j]||dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};